package binaryTree;

import java.util.HashMap;

class Class889{
    HashMap<Integer,Integer> valToIndex=new HashMap<>();
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (postorder.length!=preorder.length||postorder==null&&preorder!=null||
                postorder!=null&&preorder==null||postorder==null&&preorder==null){
            return  null;
        }
        for (int i = 0; i <postorder.length; i++) {
            valToIndex.put(postorder[i],i );
        }
        return  build(preorder,0,preorder.length-1,postorder,0,postorder.length-1);
    }
    public  TreeNode   build(int []preorder,int preStart,int preEnd,int[] postorder,int  postStart,int postEnd){
        //递归结束条件　
        if (preStart>preEnd){
            return  null;
        }
        if (preStart==preEnd){
            return  new TreeNode(preorder[preStart]);
        }
        int rootVal=preorder[preStart];

        int leftRootVal=preorder[preStart+1];
        Integer leftRootValIndex = valToIndex.get(leftRootVal);
//        TODO:此处不太对　　
//        int leftLeafNum=leftRootValIndex+1;
        int leftLeafNum=leftRootValIndex-postStart+1;


        //构建根节点
        TreeNode root = new TreeNode(rootVal);

        root.left=build(preorder,preStart+1,preStart+leftLeafNum,postorder,postStart,leftRootValIndex );
        root.right=build(preorder,preStart+leftLeafNum+1,preEnd,postorder,leftRootValIndex +1,postEnd-1);
        return  root;
    }

    public static void main(String[] args) {
        Class889 class889 = new Class889();
        int [] pre={1,2,4,5,3,6,7};
        int []  post={4,5,2,6,7,3,1};
        class889.constructFromPrePost(pre,post);

    }



}
